/*
310. 最小高度树
https://leetcode.cn/problems/minimum-height-trees/
中等 2024/11/15
*/

class Solution {
public:


    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> res;
        if(n == 1)
        {
            res.push_back(0);
            return res;
        }
        vector<vector<int>> path(n);
        vector<int> ans(n);
        for(const auto &edge : edges)
        {
            path[edge[0]].push_back(edge[1]);
            path[edge[1]].push_back(edge[0]);
            ans[edge[0]]++;
            ans[edge[1]]++;
        }


        queue<int> que;
        for(int i = 0;i < n;i++)
        {
            if(ans[i] == 1)
            {
                que.push(i);
            }
        }
        
        while(!que.empty())
        {
            res.clear();
            int n = que.size();
            
            while(n--)
            {
                int temp = que.front();
                que.pop();
                res.push_back(temp);
                for(int i = 0;i<path[temp].size();i++)
                {
                    if(--ans[path[temp][i]] == 1)
                    {
                        que.push(path[temp][i]);
                    }
                }
            }

        }
        return res;
    }
};